package com.ly.algorithm.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname Problem530
 * @Description
 *
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

输入：

1.txt
\
3
/
2

输出：
1.txt

解释：
最小绝对差为 1.txt，其中 2 和 1.txt 的差的绝对值为 1.txt（或者 2 和 3）。


提示：

树中至少有 2 个节点。
 * @Date 2020/10/12 14:21
 * @Author 冷心影翼
 */
public class Problem530 {

	public static void main(String[] args) {
		Solution530 solution530 = new Solution530();
		//[236,104,701,null,227,null,911]
		/*
			  236
			104 701
			  227  911
		 */
		TreeNode treeNode = new TreeNode(236);
		treeNode.right = new TreeNode(701);
		treeNode.right.right = new TreeNode(911);
		treeNode.left = new TreeNode(104);
		treeNode.left.right = new TreeNode(227);
		int minimumDifference = solution530.getMinimumDifference(treeNode);
		int minimumDifference2 = solution530.getMinimumDifferenceBestWay(treeNode);
		System.out.println(minimumDifference);
		System.out.println(minimumDifference2);
	}
}

class Solution530 {
	private List<Integer> list = new ArrayList<>();

	TreeNode pre = null;

	int min = Integer.MAX_VALUE;

	public int getMinimumDifference(TreeNode root) {
		order(root);
		int min = list.get(1)-list.get(0);
		list.forEach(System.out::print);
		System.out.println();
		for(int i=1;i<list.size()-1;i++) {
			int t = list.get(i+1)-list.get(i);
			min = min<t?min:t;
		}
		return min;
	}

	public int getMinimumDifferenceBestWay(TreeNode node) {
		dfs(node);
		return min;
	}

	public void dfs(TreeNode node) {
		if(node == null) {
			return;
		}
		dfs(node.left);
		if(pre != null) {
			min = Math.min(min,node.val-pre.val);
		}
		pre = node;
		dfs(node.right);
	}

	public void order(TreeNode node) {
		if(node == null) {
			return;
		}
		order(node.left);
		list.add(node.val);
		order(node.right);
	}
}